{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #切分数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #dynamic-programming #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #动态规划 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: splitArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #切分数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组 <code>nums</code> ，小李想将 <code>nums</code> 切割成若干个非空子数组，使得每个子数组最左边的数和最右边的数的最大公约数大于 1 。为了减少他的工作量，请求出最少可以切成多少个子数组。</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<blockquote>\n",
    "<p>输入：<code>nums = [2,3,3,2,3,3]</code></p>\n",
    "\n",
    "<p>输出：<code>2</code></p>\n",
    "\n",
    "<p>解释：最优切割为 [2,3,3,2] 和 [3,3] 。第一个子数组头尾数字的最大公约数为 2 ，第二个子数组头尾数字的最大公约数为 3 。</p>\n",
    "</blockquote>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<blockquote>\n",
    "<p>输入：<code>nums = [2,3,5,7]</code></p>\n",
    "\n",
    "<p>输出：<code>4</code></p>\n",
    "\n",
    "<p>解释：只有一种可行的切割：[2], [3], [5], [7]</p>\n",
    "</blockquote>\n",
    "\n",
    "<p><strong>限制：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10^5</code></li>\n",
    "\t<li><code>2 &lt;= nums[i] &lt;= 10^6</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [qie-fen-shu-zu](https://leetcode.cn/problems/qie-fen-shu-zu/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [qie-fen-shu-zu](https://leetcode.cn/problems/qie-fen-shu-zu/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,3,2,3,3]', '[2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10 ** 5\n",
    "isPrime = [True] * (N + 1)\n",
    "Prime = []\n",
    "for i in range(2, N + 1):\n",
    "    if isPrime[i]:\n",
    "        Prime.append(i)\n",
    "    for p in Prime:\n",
    "        if i * p > N:\n",
    "            break\n",
    "        isPrime[i * p] = False\n",
    "        if i % p == 0:\n",
    "            break\n",
    "\n",
    "def myprime(n):\n",
    "    ans = []\n",
    "    for p in Prime:\n",
    "        if p * p > n:\n",
    "            break\n",
    "        if n % p == 0:\n",
    "            ans.append(p)\n",
    "            while n % p == 0:\n",
    "                n //= p\n",
    "    if n > 1:\n",
    "        ans.append(n)\n",
    "    return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = [n] * n\n",
    "        ans[0] = 1\n",
    "        d = {}\n",
    "        for p in myprime(nums[0]):\n",
    "            d[p] = 1\n",
    "        for i in range(1, n):\n",
    "            for p in myprime(nums[i]):\n",
    "                d[p] = min(ans[i - 1] + 1, d.get(p, n)) \n",
    "                ans[i] = min(ans[i], d[p])\n",
    "        return ans[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10 ** 5\n",
    "isPrime = [True] * (N + 1)\n",
    "Prime = []\n",
    "for i in range(2, N + 1):\n",
    "    if isPrime[i]:\n",
    "        Prime.append(i)\n",
    "    for p in Prime:\n",
    "        if i * p > N:\n",
    "            break\n",
    "        isPrime[i * p] = False\n",
    "        if i % p == 0:\n",
    "            break\n",
    "\n",
    "def myprime(n):\n",
    "    ans = []\n",
    "    for p in Prime:\n",
    "        if p * p > n:\n",
    "            break\n",
    "        if n % p == 0:\n",
    "            ans.append(p)\n",
    "            while n % p == 0:\n",
    "                n //= p\n",
    "    if n > 1:\n",
    "        ans.append(n)\n",
    "    return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = [n] * n\n",
    "        ans[0] = 1\n",
    "        d = {}\n",
    "        for p in myprime(nums[0]):\n",
    "            d[p] = 1\n",
    "        for i in range(1, n):\n",
    "            pi = myprime(nums[i])\n",
    "            for p in pi:\n",
    "                if p in d:\n",
    "                    ans[i] = min(ans[i], d[p])\n",
    "                else:\n",
    "                    d[p] = ans[i - 1] + 1\n",
    "            ans[i] = min(ans[i], ans[i - 1] + 1)\n",
    "            for p in pi:\n",
    "                d[p] = min(ans[i - 1] + 1, d[p]) \n",
    "        return ans[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "max_num = 1000000\n",
    "min_factor = [1] * (max_num + 1)\n",
    "p = 2\n",
    "\n",
    "# O(M loglog M)\n",
    "while (p <= max_num):\n",
    "    i = p\n",
    "    while i * p <= max_num:\n",
    "        if min_factor[i * p] == 1:\n",
    "            min_factor[i * p] = p\n",
    "        i += 1\n",
    "\n",
    "    p += 1\n",
    "    while p <= max_num:\n",
    "        if min_factor[p] == 1:\n",
    "            break\n",
    "\n",
    "        p += 1\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums) -> int:\n",
    "        f = {}\n",
    "        n = len(nums)\n",
    "        \n",
    "        x = nums[0]\n",
    "        INF = 100000000\n",
    "        while True:\n",
    "            if min_factor[x] == 1:\n",
    "                f[x] = 1\n",
    "                break\n",
    "            \n",
    "            f[min_factor[x]] = 1\n",
    "            x //= min_factor[x]\n",
    "        \n",
    "        min_prev = 1\n",
    "        for i in range(1, n):\n",
    "            x = nums[i]\n",
    "            \n",
    "            min_cur = INF\n",
    "            while True:\n",
    "                if min_factor[x] == 1:\n",
    "                    f[x] = min(f.get(x, INF), min_prev + 1)     \n",
    "                    min_cur = min(min_cur, f[x])       \n",
    "                    break\n",
    "                \n",
    "                f[min_factor[x]] = min(f.get(min_factor[x], INF), min_prev + 1)\n",
    "                min_cur = min(min_cur, f[min_factor[x]])\n",
    "                x //= min_factor[x]\n",
    "\n",
    "            min_prev = min_cur\n",
    "\n",
    "        return min_prev\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "max_fac = [-1 for _ in range(1000001)]\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        if max_fac[0]==-1:\n",
    "            max_fac[0]=0\n",
    "\n",
    "            for i in range(2,1000001):\n",
    "                if max_fac[i] == -1:\n",
    "                    for val in range(i,1000001,i):\n",
    "                        max_fac[val] = i\n",
    "\n",
    "    def splitArray(self, nums: List[int]) -> int:\n",
    "        min_step={}\n",
    "        n=len(nums)\n",
    "\n",
    "        dp = 0\n",
    "        for i in range(n):\n",
    "            val = nums[i]\n",
    "            ans = i+1\n",
    "\n",
    "            while val != 1:\n",
    "                p = max_fac[val]\n",
    "                while max_fac[val] == p:\n",
    "                    val//=p\n",
    "\n",
    "                if p not in min_step:\n",
    "                    min_step[p] = dp\n",
    "                else:\n",
    "                    min_step[p] = min(min_step[p],dp)\n",
    "\n",
    "                ans = min(ans,min_step[p]+1)\n",
    "            dp = ans\n",
    "        return dp        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "max_fac = [-1 for _ in range(1000001)]\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def __init__(self):\n",
    "        # 这里取个巧，先把max_fac数组提前算出来\n",
    "        if max_fac[0] == -1:\n",
    "            max_fac[0] = 0\n",
    "\n",
    "            for i in range(2, 1000001):\n",
    "                if max_fac[i] == -1:\n",
    "                    for val in range(i, 1000001, i):\n",
    "                        # 枚举所有i的倍数，更新这些倍数的最大质因子\n",
    "                        max_fac[val] = i\n",
    "\n",
    "\n",
    "    def splitArray(self, nums: List[int]) -> int:\n",
    "        min_step = {}\n",
    "        n = len(nums)\n",
    "\n",
    "        dp = 0\n",
    "        for i in range(n):\n",
    "            val = nums[i]\n",
    "            ans = i+1\n",
    "\n",
    "            while val != 1:\n",
    "                p = max_fac[val]\n",
    "                while max_fac[val] == p:\n",
    "                    val //= p\n",
    "\n",
    "                if p not in min_step:\n",
    "                    min_step[p] = dp\n",
    "                else:\n",
    "                    min_step[p] = min(min_step[p], dp)\n",
    "\n",
    "                ans = min(ans, min_step[p] + 1)\n",
    "\n",
    "            dp = ans\n",
    "\n",
    "        return dp\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 1000001\n",
    "primes, isp = [], [True] * N\n",
    "isp[0] = isp[1] = False\n",
    "for i in range(2, N):\n",
    "    if isp[i]:\n",
    "        primes.append(i)\n",
    "    for p in primes:\n",
    "        if (ii := i * p) >= N:\n",
    "            break\n",
    "        isp[ii] = False\n",
    "        if i % p == 0:\n",
    "            break\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> int:\n",
    "        f = defaultdict(lambda:sys.maxsize)\n",
    "        pre = 0\n",
    "        for x in nums:\n",
    "            cur = pre + 1\n",
    "            if isp[x]:\n",
    "                cur = min(f[x] + 1, cur)\n",
    "                f[x] = min(f[x], pre)\n",
    "            else:\n",
    "                for p in primes:\n",
    "                    a, b = divmod(x, p)\n",
    "                    if b == 0:\n",
    "                        if p in f:\n",
    "                            cur = min(f[p] + 1, cur)\n",
    "                        if isp[a]:\n",
    "                            cur = min(f[a] + 1, cur) # ㈠\n",
    "                        f[p] = min(f[p], pre)\n",
    "                        if isp[a] and a != p: # 如果 x / p 是素数，可以提前终止\n",
    "                            f[a] = min(f[a], pre)\n",
    "                            break\n",
    "                    if p * p >= x:\n",
    "                        # 只遍历 sqrt(x) 之前的所有素数，如果存在大于sqrt(x)的素数因子，必然在处理 ㈠ 中处理到\n",
    "                        # 这样可以大量减少无效遍历\n",
    "                        break\n",
    "            pre = cur\n",
    "        return pre\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 1000001\n",
    "\n",
    "primes, isp = [], [True] * N\n",
    "\n",
    "isp[0] = isp[1] = False\n",
    "\n",
    "for i in range(2, N):\n",
    "\n",
    "    if isp[i]:\n",
    "\n",
    "        primes.append(i)\n",
    "\n",
    "    for p in primes:\n",
    "\n",
    "        if (ii := i * p) >= N:\n",
    "\n",
    "            break\n",
    "\n",
    "        isp[ii] = False\n",
    "\n",
    "        if i % p == 0:\n",
    "\n",
    "            break\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def splitArray(self, nums: List[int]) -> int:\n",
    "\n",
    "        f = defaultdict(lambda:sys.maxsize)\n",
    "\n",
    "        pre = 0\n",
    "\n",
    "        for x in nums:\n",
    "\n",
    "            cur = pre + 1\n",
    "\n",
    "            if isp[x]:\n",
    "\n",
    "                cur = min(f[x] + 1, cur)\n",
    "\n",
    "                f[x] = min(f[x], pre)\n",
    "\n",
    "            else:\n",
    "\n",
    "                for p in primes:\n",
    "\n",
    "                    a, b = divmod(x, p)\n",
    "\n",
    "                    if b == 0:\n",
    "\n",
    "                        if p in f:\n",
    "\n",
    "                            cur = min(f[p] + 1, cur)\n",
    "\n",
    "                        if isp[a]:\n",
    "\n",
    "                            cur = min(f[a] + 1, cur) # ㈠\n",
    "\n",
    "                        f[p] = min(f[p], pre)\n",
    "\n",
    "                        if isp[a] and a != p: # 如果 x / p 是素数，可以提前终止\n",
    "\n",
    "                            f[a] = min(f[a], pre)\n",
    "\n",
    "                            break\n",
    "\n",
    "                    if p * p >= x:\n",
    "\n",
    "                        # 只遍历 sqrt(x) 之前的所有素数，如果存在大于sqrt(x)的素数因子，必然在处理 ㈠ 中处理到\n",
    "\n",
    "                        # 这样可以大量减少无效遍历\n",
    "\n",
    "                        break\n",
    "\n",
    "            pre = cur\n",
    "\n",
    "        return pre\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 1000001\n",
    "primes, isp = [], [True] * N\n",
    "isp[0] = isp[1] = False\n",
    "for i in range(2, N):\n",
    "    if isp[i]:\n",
    "        primes.append(i)\n",
    "    for p in primes:\n",
    "        if (ii := i * p) >= N:\n",
    "            break\n",
    "        isp[ii] = False\n",
    "        if i % p == 0:\n",
    "            break\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> int:\n",
    "        f = defaultdict(lambda:sys.maxsize)\n",
    "        pre = 0\n",
    "        for x in nums:\n",
    "            cur = pre + 1\n",
    "            if isp[x]:\n",
    "                cur = min(f[x] + 1, cur)\n",
    "                f[x] = min(f[x], pre)\n",
    "            else:\n",
    "                for p in primes:\n",
    "                    a, b = divmod(x, p)\n",
    "                    if b == 0:\n",
    "                        if p in f:\n",
    "                            cur = min(f[p] + 1, cur)\n",
    "                        if isp[a]:\n",
    "                            cur = min(f[a] + 1, cur) # ㈠\n",
    "                        f[p] = min(f[p], pre)\n",
    "                        if isp[a] and a != p: # 如果 x / p 是素数，可以提前终止\n",
    "                            f[a] = min(f[a], pre)\n",
    "                            break\n",
    "                    if p * p >= x:\n",
    "                        # 只遍历 sqrt(x) 之前的所有素数，如果存在大于sqrt(x)的素数因子，必然在处理 ㈠ 中处理到\n",
    "                        # 这样可以大量减少无效遍历\n",
    "                        break\n",
    "            pre = cur\n",
    "        return pre\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 1000001\n",
    "primes, isp = [], [True] * N\n",
    "isp[0] = isp[1] = False\n",
    "for i in range(2, N):\n",
    "    if isp[i]:\n",
    "        primes.append(i)\n",
    "    for p in primes:\n",
    "        if (ii := i * p) >= N:\n",
    "            break\n",
    "        isp[ii] = False\n",
    "        if i % p == 0:\n",
    "            break\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> int:\n",
    "        f = defaultdict(lambda:sys.maxsize)\n",
    "        pre = 0\n",
    "        for x in nums:\n",
    "            cur = pre + 1\n",
    "            if isp[x]:\n",
    "                cur = min(f[x] + 1, cur)\n",
    "                f[x] = min(f[x], pre)\n",
    "            else:\n",
    "                for p in primes:\n",
    "                    a, b = divmod(x, p)\n",
    "                    if b == 0:\n",
    "                        if p in f:\n",
    "                            cur = min(f[p] + 1, cur)\n",
    "                        if isp[a]:\n",
    "                            cur = min(f[a] + 1, cur) # ㈠\n",
    "                        f[p] = min(f[p], pre)\n",
    "                        if isp[a] and a != p: # 如果 x / p 是素数，可以提前终止\n",
    "                            f[a] = min(f[a], pre)\n",
    "                            break\n",
    "                    if p * p >= x:\n",
    "                        break\n",
    "            pre = cur\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 1000001\n",
    "primes, isp = [], [True] * N\n",
    "isp[0] = isp[1] = False\n",
    "for i in range(2, N):\n",
    "    if isp[i]:\n",
    "        primes.append(i)\n",
    "    for p in primes:\n",
    "        if (ii := i * p) >= N:\n",
    "            break\n",
    "        isp[ii] = False\n",
    "        if i % p == 0:\n",
    "            break\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> int:\n",
    "        f = defaultdict(lambda:sys.maxsize)\n",
    "        pre = 0\n",
    "        for x in nums:\n",
    "            cur = pre + 1\n",
    "            if isp[x]:\n",
    "                cur = min(f[x] + 1, cur)\n",
    "                f[x] = min(f[x], pre)\n",
    "            else:\n",
    "                for p in primes:\n",
    "                    a, b = divmod(x, p)\n",
    "                    if b == 0:\n",
    "                        if p in f:\n",
    "                            cur = min(f[p] + 1, cur)\n",
    "                        if isp[a]:\n",
    "                            cur = min(f[a] + 1, cur) # ㈠\n",
    "                        f[p] = min(f[p], pre)\n",
    "                        if isp[a] and a != p: # 如果 x / p 是素数，可以提前终止\n",
    "                            f[a] = min(f[a], pre)\n",
    "                            break\n",
    "                    if p * p >= x:\n",
    "                        # 只遍历 sqrt(x) 之前的所有素数，如果存在大于sqrt(x)的素数因子，必然在处理 ㈠ 中处理到\n",
    "                        # 这样可以大量减少无效遍历\n",
    "                        break\n",
    "            pre = cur\n",
    "        return pre\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 素数筛， 预处理备用\n",
    "MX = 1000001\n",
    "isprime, primes = [True] * MX, []\n",
    "for i in range(2, MX):\n",
    "    if isprime[i]:\n",
    "        primes.append(i)\n",
    "        for j in range(i * i, MX, i):\n",
    "            isprime[j] = False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> int:\n",
    "            from collections import defaultdict\n",
    "            '''\n",
    "                dct: 记录出现的素数前一位最小切分数\n",
    "                pre: (顺序遍历)记录截止前一位的切分数\n",
    "            '''\n",
    "            dct, pre = defaultdict(lambda: float('inf')), 0\n",
    "\n",
    "            for i, n in enumerate(nums):\n",
    "                # 当前位最大切分数就是前一位+1\n",
    "                cur = pre + 1\n",
    "                # 如果当前位本身为素数，可以与之前出现过的位置\"合并\"\n",
    "                # 并且可以刷新该素数的前一位最小切分数\n",
    "                if isprime[n]:\n",
    "                    cur = min(cur, dct[n] + 1)\n",
    "                    dct[n] = min(dct[n], pre)\n",
    "                else:\n",
    "                    # 如果n不是素数，提取质因数\n",
    "                    for p in primes:\n",
    "                        mul, rest = n // p, n % p\n",
    "                        if rest == 0:\n",
    "                            if p in dct:\n",
    "                                # 与前序结果合并刷新\n",
    "                                cur = min(cur, dct[p] + 1)\n",
    "                            # 刷新该素数最优值\n",
    "                            dct[p] = min(dct[p], pre)\n",
    "                            # 如果商也为素数，同样逻辑处理(只可能出现一次)\n",
    "                            if isprime[mul]:\n",
    "                                cur = min(cur, dct[mul] + 1)\n",
    "                                if mul != p:\n",
    "                                    dct[mul] = min(dct[mul], pre)\n",
    "                                    break\n",
    "                        # 剪枝\n",
    "                        if p * p >= n:\n",
    "                            break\n",
    "                # 一维滚动更新\n",
    "                pre = cur\n",
    "\n",
    "            return pre\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MAX=1000000\n",
    "p = 2\n",
    "min_factor = [1] * (MAX + 1)\n",
    "while (p <= MAX):\n",
    "    i = p\n",
    "    min_factor[p]=p\n",
    "    while i * p <= MAX:\n",
    "        if min_factor[i * p] == 1:\n",
    "            min_factor[i * p] = p\n",
    "        i += 1\n",
    "\n",
    "    p += 1\n",
    "    while p <= MAX:\n",
    "        if min_factor[p] == 1:\n",
    "            break\n",
    "        p += 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[n]*(MAX+1)\n",
    "        f=[n]*(n+1)\n",
    "        f[0]=0\n",
    "        for idx,num in enumerate(nums):\n",
    "            i=num\n",
    "            while i>1:\n",
    "                cur=min_factor[i]\n",
    "                if dp[cur]>f[idx]:\n",
    "                    dp[cur]=f[idx]\n",
    "                if dp[cur]+1<f[idx+1]:\n",
    "                    f[idx+1] = dp[cur]+1\n",
    "                i=i//cur\n",
    "\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "MX = 1000001\n",
    "isprime = [True] * MX\n",
    "primes = []\n",
    "for i in range(2, MX):\n",
    "    if isprime[i]:\n",
    "        primes.append(i)\n",
    "        for j in range(i * i, MX, i):\n",
    "            isprime[j] = False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> int:\n",
    "            from collections import defaultdict\n",
    "            dct, pre = defaultdict(lambda: float('inf')), 0\n",
    "\n",
    "            for i, n in enumerate(nums):\n",
    "                cur = pre + 1\n",
    "                if isprime[n]:\n",
    "                    cur = min(cur, dct[n] + 1)\n",
    "                    dct[n] = min(dct[n], pre)\n",
    "\n",
    "                else:\n",
    "                    for p in primes:\n",
    "                        mul, rest = n // p, n % p\n",
    "                        if rest == 0:\n",
    "                            if p in dct:\n",
    "                                cur = min(cur, dct[p] + 1)\n",
    "\n",
    "                            dct[p] = min(dct[p], pre)\n",
    "\n",
    "                            if isprime[mul]:\n",
    "                                cur = min(cur, dct[mul] + 1)\n",
    "                                if mul != p:\n",
    "                                    dct[mul] = min(dct[mul], pre)\n",
    "                                    break\n",
    "\n",
    "                        if p * p >= n:\n",
    "                            break\n",
    "                pre = cur\n",
    "\n",
    "            return pre\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 1000001\n",
    "primes, isp = [], [True] * N\n",
    "isp[0] = isp[1] = False\n",
    "for i in range(2, N):\n",
    "    if isp[i]:\n",
    "        primes.append(i)\n",
    "    for p in primes:\n",
    "        if (ii := i * p) >= N:\n",
    "            break\n",
    "        isp[ii] = False\n",
    "        if i % p == 0:\n",
    "            break\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> int:\n",
    "        f = defaultdict(lambda:sys.maxsize)\n",
    "        pre = 0\n",
    "        for x in nums:\n",
    "            cur = pre + 1\n",
    "            if isp[x]:\n",
    "                cur = min(f[x] + 1, cur)\n",
    "                f[x] = min(f[x], pre)\n",
    "            else:\n",
    "                for p in primes:\n",
    "                    a, b = divmod(x, p)\n",
    "                    if b == 0:\n",
    "                        if p in f:\n",
    "                            cur = min(f[p] + 1, cur)\n",
    "                        if isp[a]:\n",
    "                            cur = min(f[a] + 1, cur) # ㈠\n",
    "                        f[p] = min(f[p], pre)\n",
    "                        if isp[a] and a != p: # 如果 x / p 是素数，可以提前终止\n",
    "                            f[a] = min(f[a], pre)\n",
    "                            break\n",
    "                    if p * p >= x:\n",
    "                        # 只遍历 sqrt(x) 之前的所有素数，如果存在大于sqrt(x)的素数因子，必然在处理 ㈠ 中处理到\n",
    "                        # 这样可以大量减少无效遍历\n",
    "                        break\n",
    "            pre = cur\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "N = 10 ** 6\n",
    "isPrime = [True] * (N + 1)\n",
    "Prime = []\n",
    "for i in range(2, N + 1):\n",
    "    if isPrime[i]:\n",
    "        Prime.append(i)\n",
    "    for p in Prime:\n",
    "        if i * p > N:\n",
    "            break\n",
    "        isPrime[i * p] = False\n",
    "        if i % p == 0:\n",
    "            break\n",
    "\n",
    "def myprime(n):\n",
    "    ans = []\n",
    "    for p in Prime:\n",
    "        if p * p > n:\n",
    "            break\n",
    "        if n % p == 0:\n",
    "            ans.append(p)\n",
    "            while n % p == 0:\n",
    "                n //= p\n",
    "    if n > 1:\n",
    "        ans.append(n)\n",
    "    return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = [n] * n\n",
    "        ans[0] = 1\n",
    "        d = {}\n",
    "        for p in myprime(nums[0]):\n",
    "            d[p] = 1\n",
    "        for i in range(1, n):\n",
    "            for p in myprime(nums[i]):\n",
    "                d[p] = min(ans[i - 1] + 1, d.get(p, n)) \n",
    "                ans[i] = min(ans[i], d[p])\n",
    "        return ans[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class PrimeTable:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.n = n\n",
    "        self.primes = []\n",
    "        self.min_div = [0] * (n + 1)\n",
    "        self.min_div[1] = 1\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            if not self.min_div[i]:\n",
    "                self.primes.append(i)\n",
    "                self.min_div[i] = i\n",
    "\n",
    "            for p in self.primes:\n",
    "                if i * p > n:\n",
    "                    break\n",
    "                self.min_div[i * p] = p\n",
    "                if i % p == 0:\n",
    "                    break\n",
    "\n",
    "    def is_prime(self, x: int):\n",
    "        if x < 2:\n",
    "            return False\n",
    "        if x <= self.n:\n",
    "            return self.min_div[x] == x\n",
    "\n",
    "    def prime_factorization(self, x: int):\n",
    "        while 1 < x <= self.n:\n",
    "            p, cnt = self.min_div[x], 0\n",
    "            while x % p == 0:\n",
    "                cnt += 1\n",
    "                x //= p\n",
    "            yield p, cnt\n",
    "\n",
    "pt = PrimeTable(1000001)\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * (n + 1)\n",
    "        d = {}\n",
    "        for i in range(n):\n",
    "            dp[i] = dp[i - 1] + 1\n",
    "            prime_list = []\n",
    "            for p, _ in pt.prime_factorization(nums[i]):\n",
    "                prime_list.append(p)\n",
    "            for prime in prime_list:\n",
    "                if prime in d:\n",
    "                    dp[i] = min(dp[i], d[prime] + 1)\n",
    "            for prime in prime_list:\n",
    "                if prime not in d:\n",
    "                    d[prime] = dp[i - 1]\n",
    "                else:\n",
    "                    d[prime] = min(d[prime], dp[i - 1])\n",
    "        return dp[-2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pre = [0]*1000001\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        for i in range(2, 1000001):\n",
    "            if not pre[i]:\n",
    "                for j in range(i, 1000001, i):\n",
    "                    pre[j]=i\n",
    "    def splitArray(self, s: List[int]) -> int:\n",
    "        n=len(s)\n",
    "        ppd=0\n",
    "        dpp=[n]*1000001\n",
    "        for i in range(n):\n",
    "            dp = n\n",
    "            while s[i]>1:\n",
    "                p = pre[s[i]]\n",
    "                while pre[s[i]]==p:s[i]//=p\n",
    "                dpp[p] = min(dpp[p],ppd)\n",
    "                dp = min(dp, dpp[p]+1)\n",
    "            ppd = dp\n",
    "        return dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "MX = 1000001\n",
    "isprime = [True] * MX\n",
    "primes = []\n",
    "for i in range(2, MX):\n",
    "    if isprime[i]:\n",
    "        primes.append(i)\n",
    "        for j in range(i * i, MX, i):\n",
    "            isprime[j] = False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> int:\n",
    "            from collections import defaultdict\n",
    "            dct = defaultdict(lambda: float('inf'))\n",
    "            pre = 0\n",
    "\n",
    "            for i, n in enumerate(nums):\n",
    "                #print(i, n, '--------------')\n",
    "                cur = pre + 1\n",
    "                if isprime[n]:\n",
    "\n",
    "                    cur = min(cur, dct[n] + 1)\n",
    "                    dct[n] = min(dct[n], pre)\n",
    "\n",
    "                else:\n",
    "                    for p in primes:\n",
    "                        #print(p)\n",
    "                        mul, rest = n // p, n % p\n",
    "                        if rest == 0:\n",
    "                            if p in dct:\n",
    "                                cur = min(cur, dct[p] + 1)\n",
    "\n",
    "                            dct[p] = min(dct[p], pre)\n",
    "\n",
    "                            if isprime[mul]:\n",
    "                                cur = min(cur, dct[mul] + 1)\n",
    "                                if mul != p:\n",
    "                                    dct[mul] = min(dct[mul], pre)\n",
    "\n",
    "                                    break\n",
    "\n",
    "                        if p * p >= n:\n",
    "                            break\n",
    "                pre = cur\n",
    "\n",
    "            print(dct)\n",
    "            return pre\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitArray(self, nums: List[int]) -> int:\n",
    "        def _prime_table(n):\n",
    "            prime = [1] * (n + 1)\n",
    "            for i in range(2, n+1):\n",
    "                if prime[i] == 1:\n",
    "                    prime[i] = i\n",
    "                    for j in range(i * i, n+1, i):\n",
    "                        prime[j] = i\n",
    "            return prime\n",
    "\n",
    "        prime_factor = _prime_table(10**6)\n",
    "        d = dict()\n",
    "        n = len(nums)\n",
    "        dp = [n] * (n+1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1, n+1):\n",
    "            x = nums[i-1]\n",
    "            while x > 1:\n",
    "                t = prime_factor[x]\n",
    "                if t not in d.keys():\n",
    "                    d[t] = i\n",
    "                \n",
    "                if dp[i-1] < dp[d[t] - 1]:\n",
    "                    d[t] = i\n",
    "\n",
    "                dp[i] = min(dp[i], dp[d[t] - 1] + 1)\n",
    "                x //= t\n",
    "\n",
    "        return dp[-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
